/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<int, int> index;
public:
    TreeNode* inBuildTree(vector<int> preorder,vector<int>inorder,int preorderLeft,int preorderRight,int inorderLeft,int inorderRight){
        if(preorderLeft>preorderRight){
            return nullptr;
        }
        int preorderRoot = preorderLeft;
        int inorderRoot = index[preorder[preorderRoot]];
        //构造树的根节点
        TreeNode* root = new TreeNode(preorder[preorderRoot]);
        //求出左子树大小然后构造左子树，iorder左边的部分是其左子树，preorder的最右边根据子树长度确定
        int leftSize = inorderRoot-inorderLeft;
        root->left=inBuildTree(preorder,inorder,preorderLeft+1,preorderLeft+leftSize,inorderLeft,inorderRoot-1);
        //构造右子树，inorder右边的部分是其右子树，preorder的最左边根据子树长度确定
        root->right = inBuildTree(preorder,inorder,preorderLeft+leftSize+1,preorderRight,inorderRoot+1,inorderRight);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        //四个参数分别表示当前树的前序和中序序列的第一个和最后一个元素的小标值
        return inBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
};
